package algo.A05_其他排序算法;

import util.ArrayUtil;

/**
 * 用数组表示一棵树，已知某个结点的下标i，求子结点和父结点下标。
 * 左子结点：2i + 1
 * 右子结点：2i + 2
 * 父结点：(i - 1) / 2
 * <p>
 * 大顶堆：任意节点的值都 大于 子节点 的值，即根节点更大
 * 小顶堆：任意节点的值都 小于 子节点 的值，即根节点更小
 */


public class M02_堆排序_小顶堆 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 0, 30);
        ArrayUtil.print(arr);
        heapSort(arr);
        ArrayUtil.print(arr);
    }

    /**
     * 堆排序入口
     * @param arr
     */
    private static void heapSort(int[] arr){
        //构建小顶堆
        build_minHeap(arr);
        for (int i = arr.length - 1;i > 0;i--){
            //把堆顶的元素和最后一个元素对调，此时最小的元素放在了最后
            ArrayUtil.swap(arr,0,i);
            //缩小堆的范围，维护剩余元素堆的性质
            heapify(arr,0,i);//第三个参数是数组长度，因此此处i不减1
        }
    }

    /**
     * 构建小顶堆(根结点小，子结点大，大的往下走，小的往上走)
     *
     * @param arr
     * @return
     */
    private static void build_minHeap(int[] arr) {
        //从最后一个结点的父结点开始，从后往前逐个建堆
        //父结点公式：(i - 1) / 2
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }

    /**
     * 维护堆的性质(对话)
     * 小顶堆的向下调整，将当前根节点和左右孩子调整为满足小顶堆的性质
     * 当某个结点不满足小顶堆时，将该结点的最小子结点与根节点交换
     * 最终让数组完全满足小顶堆的性质
     * @param arr
     * @param root   根节点下标
     * @param length 数组长度
     */
    private static void heapify(int[] arr, int root, int length) {
        int min_index = root;//min指向值最小的结点，先假设根节点是最小的
        int left = 2 * root + 1;//左子树下标
        int right = 2 * root + 2;//右子树下标
        //左孩子未越界且左孩子的值小于最小的结点
        if (left < length && arr[left] < arr[min_index]){
            //修改最小的结点为左孩子
            min_index = left;
        }
        //右孩子未越界且右孩子的值小于最小的结点
        if (right < length && arr[right] < arr[min_index]){
            //修改最小的结点为右孩子
            min_index = right;
        }
        //如果此时最小的结点不是根节点，则需要做交换
        if (min_index != root){
            ArrayUtil.swap(arr,min_index,root);
            //交换之后要再次维护左孩子的左右子树是否满足堆的性质
            heapify(arr,min_index,length);
        }
    }
}
